#include <cstdio>
#include <iostream>

using namespace std;

#define GRAPH_SIZE 100

typedef int T;

/****
	* Graph in Matrix
	**************************************************/

class MGraph
{
public:
    MGraph(bool _undirected = true);
    void reset();
    T getEdge(int from, int to)
        { return mat[from][to]; }
    ///unweighted graph
    void addEdge(int from, int to)
        { mat[from][to] = 1; if(undirected) mat[to][from] = 1; }
    void delEdge(int from, int to)
        { mat[from][to] = 0; if(undirected) mat[to][from] = 0; }

    ///weighted graph
    void setEdgeWeight(int from, int to, T val)
        { mat[from][to] = val; if(undirected) mat[to][from] = val;}
    void addEdgeWeight(int from, int to, T val)
        { mat[from][to] += val; if(undirected) mat[to][from] += val;}
    void subEdgeWeight(int from, int to, T val)
        { if(undirected) mat[from][to] = mat[to][from] = (mat[from][to] >= val)? mat[from][to] - val : 0; }

private:
    T mat[GRAPH_SIZE][GRAPH_SIZE];
    bool undirected;
};

MGraph::MGraph(bool _undirected) : undirected(_undirected)
{
    for(int i = 0; i < GRAPH_SIZE; i++)
        for(int j = 0; j < GRAPH_SIZE; j++)
            mat[i][j] = 0;
}

void MGraph::reset()
{
    for(int i = 0; i < GRAPH_SIZE; i++)
        for(int j = 0; j < GRAPH_SIZE; j++)
            mat[i][j] = 0;
}



/****
	* Linked Graph with unmaped edge(Not easy to find the reverse edge)
	****************************************************/
class LinkedGraphS
{
public:
    LinkedGraphS(int _nodeLimit = 100, int _edgeLimit = 1000, int _trashCapcity = 1000)
        : nodeLimit(_nodeLimit), edgeLimit( _edgeLimit), edgeEndPos(0), trashCapcity(_trashCapcity), curTrashSize(0)
    {
        nodes = new int[nodeLimit];
        edgeFrom = new int[edgeLimit];
        edgeTo = new int[edgeLimit];
        nextEdge = new int[edgeLimit];
        edges = new T[edgeLimit];
        edgeTrash = new int[trashCapcity];
        for(int i = 0; i < nodeLimit; i++)
            nodes[i] = -1;
    }

    T& addEdge(int from, int to, T val = 1)
    {
        int index = -1;
        /***uncomment to make sure no repeated edges**/
//        if((index = getEdge(from, to)) != -1)
//            return edges[index] = val;
        index = newEdge(from, to, val);
        nextEdge[index] = nodes[from];
        nodes[from] = index;
        return edges[index];
    }

    ///return the index of edge which have been removed
    int removeEdge(int from, int to)
    {
        int pos = nodes[from];
        int *pre = &nodes[from];
        while(pos != -1)
        {
            if(edgeTo[pos] == to)
                return *pre = nextEdge[pos], pos;
            pre = &nextEdge[pos];
            pos = nextEdge[pos];
        }
        return pos;
    }

    int removeEdge(int index)
    {
        return removeEdge(edgeFrom[index], edgeTo[index]);
    }
    ///get edge val from it's index
    T& operator[](int index)
    {
        return edges[index];
    }

    T& getEdgeVal(int index)
    {
        return edges[index];
    }

    ///get edge's index
    int getEdge(int from, int to)
    {
        int pos = nodes[from];
        while(pos != -1)
        {
            if(edgeTo[pos] == to)
                return pos;
            pos = nextEdge[pos];
        }
        return -1;
    }

    ///get next edge by index
    int getNextEdge(int edgeIndex)
    {
        return nextEdge[edgeIndex];
    }

    /***For weighted edge***/
    T& setWeight(int from, int to, int val)
    {
        int index = -1;
        if((index = getEdge(from, to) ) != -1)
            return edges[index] = val;
        return addEdge(from, to, val);
    }

    T& addWeight(int from, int to, int val)
    {
        int index = -1;
        if((index = getEdge(from, to) ) != -1)
            return edges[index] += val;
        return addEdge(from, to, val);
    }

    ///you will the edge would be removed if it is not positive
    T subWeight(int from, int to, int val)
    {
        int index = -1;
        if((index = getEdge(from, to) ) != -1)
        {
            edges[index] -= val;
            if(edges[index] <= 0)
                removeEdge(index);
            return edges[index];
        }
        return 0;
    }


private:
    ///return index
    int newEdge(int from, int to, T val = 1)
    {
        if(curTrashSize)
        {
            int index = --curTrashSize;
            edgeFrom[index] = from;
            edgeTo[index] = to;
            edges[index] = val;
            nextEdge[index] = -1;
            return edgeTrash[index];
        }
        edgeFrom[edgeEndPos] = from;
        edgeTo[edgeEndPos] = to;
        edges[edgeEndPos] = val;
        nextEdge[edgeEndPos] = -1;
        return edgeEndPos++;
    }

    ///return next edge of removeed edge
    int trashEdge(int index)
    {
        edgeTrash[curTrashSize++] = index;
        return nextEdge[index];
    }

    int nodeLimit;
    int edgeLimit;
    int edgeEndPos;
    int trashCapcity;
    int curTrashSize;
    int* nodes;
    int* edgeFrom;
    int* edgeTo;
    T* edges;
    int* nextEdge;
    int* edgeTrash;  ///a stack
};



class LinkedGraphD
{

};
